<HTML>
<HEAD>
<TITLE>
MapHashTable.h
</TITLE>
</HEAD>
<BODY>
<PRE>
<font color="green">/*
* Copyright 2006 the original author or authors.
* 
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* 
*      http://www.apache.org/licenses/LICENSE-2.0
* 
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/</font>

<font color="blue">#ifndef</font> AUTUMN_MAPHASHTABLE_H
<font color="blue">#define</font> AUTUMN_MAPHASHTABLE_H

<font color="blue">#include</font> <font color="maroon">&#60;map&#62;</font>

<font color="blue">using</font> <font color="blue">namespace</font> std;

<font color="blue">namespace</font> Autumn<font color="black">{</font>

<font color="green">/** 
 * Hash table template using map.
 * @param E Element type, must support operator "="
 * @param K Key type
 * @version 0.1.0
 * @since 2006-12-8
 */</font>

<font color="blue">template</font><font color="black">&#60;</font><font color="blue">class</font> E, <font color="blue">class</font> K<font color="black">&#62;</font> <font color="blue">class</font> MapHashTable<font color="black">{</font>
<font color="blue">private</font><font color="black">:</font>
    <font color="green">/** The number of positons in hash table */</font>
    <font color="blue">int</font> Divisor;

    <font color="green">/** Map array */</font>
    map<font color="black">&#60;</font>K, E<font color="black">&#62;</font> <font color="black">*</font>HashTable;

<font color="blue">public</font><font color="black">:</font>
    <font color="green">/** Constructor */</font>
    MapHashTable<font color="black">(</font><font color="blue">int</font> divisor<font color="black">)</font><font color="black">{</font>
        <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>Divisor <font color="black">=</font> divisor;
        <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable <font color="black">=</font> <font color="blue">new</font> map<font color="black">&#60;</font>K, E<font color="black">&#62;</font><font color="black">[</font>divisor<font color="black">]</font>;
    <font color="black">}</font>

    <font color="green">/** Destructor */</font>
    ~MapHashTable<font color="black">(</font><font color="black">)</font><font color="black">{</font>
        <font color="blue">delete</font><font color="black">[</font><font color="black">]</font> <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable;
    <font color="black">}</font>

    <font color="green">/** 
     * Search a element by a key 
     * @param k The key of the element to search
     * @param e To save the searched element
     * @return True if find the element, false if not
     */</font>
    <font color="blue">bool</font> searchElement<font color="black">(</font><font color="blue">const</font> K<font color="black">&</font> key, E<font color="black">&</font> e<font color="black">)</font> <font color="blue">const</font>;

    <font color="green">/** Insert distinctly a element into hash table */</font>
    <font color="blue">void</font> insertElement<font color="black">(</font><font color="blue">const</font> K<font color="black">&</font> key, E<font color="black">&</font> e<font color="black">)</font>;

    <font color="green">/** 
     * Delete a element by a key 
     * @param k The key of the element to delete
     * @param e To save the deleted element
     * @return True if find the element, false if not
     */</font>
    <font color="blue">bool</font> deleteElement<font color="black">(</font><font color="blue">const</font> K<font color="black">&</font> key, E<font color="black">&</font> e<font color="black">)</font>;
    
    <font color="green">/** List all elements in hash table */</font>
    <font color="blue">void</font> listElement<font color="black">(</font>map<font color="black">&#60;</font>K, E<font color="black">&#62;</font><font color="black">&</font> m<font color="black">)</font>;
<font color="black">}</font>;

    
<font color="blue">template</font><font color="black">&#60;</font><font color="blue">class</font> E, <font color="blue">class</font> K<font color="black">&#62;</font> <font color="blue">bool</font> MapHashTable<font color="black">&#60;</font>E, K<font color="black">&#62;</font><font color="black">:</font><font color="black">:</font>
searchElement<font color="black">(</font><font color="blue">const</font> K<font color="black">&</font> key, E<font color="black">&</font> e<font color="black">)</font> <font color="blue">const</font> <font color="black">{</font>
    typename map<font color="black">&#60;</font>K, E<font color="black">&#62;</font><font color="black">:</font><font color="black">:</font>iterator it <font color="black">=</font> <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable<font color="black">[</font>key % <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>Divisor<font color="black">]</font>.find<font color="black">(</font>key<font color="black">)</font>;
    <font color="blue">if</font><font color="black">(</font> it <font color="black">!</font><font color="black">=</font> <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable<font color="black">[</font>key % <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>Divisor<font color="black">]</font>.end<font color="black">(</font><font color="black">)</font> <font color="black">)</font><font color="black">{</font>
        e <font color="black">=</font> it<font color="black">-</font><font color="black">&#62;</font>second;
        <font color="blue">return</font> <font color="blue">true</font>;
    <font color="black">}</font>
    <font color="blue">return</font> <font color="blue">false</font>; 
<font color="black">}</font>

<font color="green">/** Insert distinctly a element into hash table */</font>
<font color="blue">template</font><font color="black">&#60;</font><font color="blue">class</font> E, <font color="blue">class</font> K<font color="black">&#62;</font> <font color="blue">void</font> MapHashTable<font color="black">&#60;</font>E, K<font color="black">&#62;</font><font color="black">:</font><font color="black">:</font>
insertElement<font color="black">(</font><font color="blue">const</font> K<font color="black">&</font> key, E<font color="black">&</font> e<font color="black">)</font><font color="black">{</font>
    typename map<font color="black">&#60;</font>K, E<font color="black">&#62;</font><font color="black">:</font><font color="black">:</font>iterator it <font color="black">=</font> <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable<font color="black">[</font>key % <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>Divisor<font color="black">]</font>.find<font color="black">(</font>key<font color="black">)</font>;
    <font color="blue">if</font><font color="black">(</font> it <font color="black">!</font><font color="black">=</font> <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable<font color="black">[</font>key % <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>Divisor<font color="black">]</font>.end<font color="black">(</font><font color="black">)</font> <font color="black">)</font><font color="black">{</font>
        it<font color="black">-</font><font color="black">&#62;</font>second <font color="black">=</font> e;
    <font color="black">}</font>
    <font color="blue">else</font><font color="black">{</font>
        <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable<font color="black">[</font>key % <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>Divisor<font color="black">]</font>.insert<font color="black">(</font>make_pair<font color="black">(</font>key, e<font color="black">)</font><font color="black">)</font>;
    <font color="black">}</font>
    
<font color="black">}</font>

<font color="green">/** Delete a element by a key */</font>
<font color="blue">template</font><font color="black">&#60;</font><font color="blue">class</font> E, <font color="blue">class</font> K<font color="black">&#62;</font> <font color="blue">bool</font> MapHashTable<font color="black">&#60;</font>E, K<font color="black">&#62;</font><font color="black">:</font><font color="black">:</font>
deleteElement<font color="black">(</font><font color="blue">const</font> K<font color="black">&</font> key, E<font color="black">&</font> e<font color="black">)</font><font color="black">{</font>
    typename map<font color="black">&#60;</font>K, E<font color="black">&#62;</font><font color="black">:</font><font color="black">:</font>iterator it <font color="black">=</font> <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable<font color="black">[</font>key % <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>Divisor<font color="black">]</font>.find<font color="black">(</font>key<font color="black">)</font>;
    <font color="blue">if</font><font color="black">(</font> it <font color="black">!</font><font color="black">=</font> <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable<font color="black">[</font>key % <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>Divisor<font color="black">]</font>.end<font color="black">(</font><font color="black">)</font> <font color="black">)</font><font color="black">{</font>
        e <font color="black">=</font> it<font color="black">-</font><font color="black">&#62;</font>second;
        <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable<font color="black">[</font>key % <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>Divisor<font color="black">]</font>.erase<font color="black">(</font>it<font color="black">)</font>;
        <font color="blue">return</font> <font color="blue">true</font>;
    <font color="black">}</font>
    <font color="blue">return</font> <font color="blue">false</font>;
<font color="black">}</font>

<font color="green">/** List all elements in hash table */</font>
<font color="blue">template</font><font color="black">&#60;</font><font color="blue">class</font> E, <font color="blue">class</font> K<font color="black">&#62;</font> <font color="blue">void</font> MapHashTable<font color="black">&#60;</font>E, K<font color="black">&#62;</font><font color="black">:</font><font color="black">:</font>
listElement<font color="black">(</font>map<font color="black">&#60;</font>K, E<font color="black">&#62;</font><font color="black">&</font> m<font color="black">)</font><font color="black">{</font>
    <font color="blue">for</font><font color="black">(</font><font color="blue">int</font> i<font color="black">=</font><font color="maroon">0</font>; i<font color="black">&#60;</font><font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>Divisor; i<font color="black">+</font><font color="black">+</font><font color="black">)</font><font color="black">{</font>
        <font color="blue">for</font><font color="black">(</font>typename map<font color="black">&#60;</font>K, E<font color="black">&#62;</font><font color="black">:</font><font color="black">:</font>iterator it <font color="black">=</font> <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable<font color="black">[</font>i<font color="black">]</font>.begin<font color="black">(</font><font color="black">)</font>;
                it <font color="black">!</font><font color="black">=</font> <font color="blue">this</font><font color="black">-</font><font color="black">&#62;</font>HashTable<font color="black">[</font>i<font color="black">]</font>.end<font color="black">(</font><font color="black">)</font>; it<font color="black">+</font><font color="black">+</font><font color="black">)</font> <font color="black">{</font>
            m.insert<font color="black">(</font>make_pair<font color="black">(</font>it<font color="black">-</font><font color="black">&#62;</font>first, it<font color="black">-</font><font color="black">&#62;</font>second<font color="black">)</font><font color="black">)</font>;
        <font color="black">}</font>
    <font color="black">}</font>
<font color="black">}</font>

<font color="black">}</font> <font color="green">// End namespace Autumn</font>

<font color="blue">#endif</font>

</PRE>
</BODY>
</HTML>
